{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 基本的概念"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 默认就是十进制\n",
    "a = 40\n",
    "b = (a + 30) * 2\n",
    "\n",
    "# 0b放在数值开头标识二进制数\n",
    "b1 = 0b10  # 数值2\n",
    "b2 = 0b1100 # 数值12\n",
    "\n",
    "print(b1)      # 2\n",
    "print(bin(b1)) # '0b10'\n",
    "\n",
    "# 0o放在数值开头标识八进制数\n",
    "o1 = 0o10    # 数值8\n",
    "\n",
    "# 0x放在数值开头标识十六进制数\n",
    "x1 = 0xf     # 数值15\n",
    "x2 = 0x1a    # 数值26\n",
    "\n",
    "\n",
    "print(o1)      # 8\n",
    "print(oct(o1)) # '0o10'\n",
    "print(x1)      # 15\n",
    "print(hex(x1)) # '0xf'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 进制转换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(bin(0o7))  # 八进制转二进制\n",
    "print(hex(0b1111)) # 二进制转换十六进制\n",
    "print(int('0b111', 2)) # 二进制转换十进制\n",
    "print(int('111', 2)) # 不加二进制标识也是可以"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 验证二进制转十进制"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 编写一个函数，验证公式，data是一个二进制的数用，然后用字符串来表示\n",
    "def change_2_to_10(data):\n",
    "    weight = 0   # 位权位置，从0开始\n",
    "    result = 0   # 最后结果，成为一个十进制数\n",
    "    formula = \"\" # 把公式列出了\n",
    "    for num in data[::-1]:\n",
    "        result = result + int(num)*pow(2,weight)\n",
    "        formula = \"{}*2^{}+{}\".format(num, weight, formula)\n",
    "        weight += 1\n",
    "    \n",
    "    print(\"计算得到结果:\", result)  # 输出结果\n",
    "    print(\"内置函数的结果:\", int(data,2))  # 输出结果\n",
    "    print(\"算式:\", formula[:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "change_2_to_10('1１0')   # 0b10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 验证八进制转十进制"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data是一个n进制的数，用字符串来表示\n",
    "def change_8_to_10(data):\n",
    "    weight = 0   # 位权位置，从0开始\n",
    "    result = 0   # 最后结果，成为一个十进制数\n",
    "    formula = \"\" # 把公式列出了\n",
    "    for num in data[::-1]:\n",
    "        result = result + int(num)*pow(8,weight)  # 基数变成8\n",
    "        formula = \"{}*8^{}+{}\".format(num, weight, formula)  # 把2变成8\n",
    "        weight += 1\n",
    "    \n",
    "    print(\"计算得到结果:\", result)  # 输出结果\n",
    "    print(\"内置函数的结果:\", int(data,8))  # 输出结果\n",
    "    print(\"算式:\", formula[:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "change_8_to_10('1777')   # 0b10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 十进制转化为二进制"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def change_10_to_2(data):\n",
    "    input_data = data\n",
    "    result = []    # 保存每次余数\n",
    "    quotient = data \n",
    "    while quotient > 0:  # 直到商为0才结束\n",
    "        quotient =  data // 2\n",
    "        remainder = data % 2\n",
    "        result.append(remainder)\n",
    "        print(\"{d} / 2 = {q}, 余数为{r}\".format(d=data, q=quotient, r=remainder))\n",
    "        data = quotient\n",
    "    \n",
    "    remainder_list = \",\".join([str(i) for i in result]) # join可以把列表聚合为一个字符串\n",
    "    rever = \"\".join([str(i) for i in result[::-1]])                      \n",
    "    print(\"上面的余数为{}。逆排列后变为{}\".format(remainder_list, rever))\n",
    "    print(\"内置函数的结果:\", bin(input_data))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "change_10_to_2(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：网络攻击"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def change_10_to_2(i): \n",
    "    \"\"\"\n",
    "    找出IP地址每一组二进制数的情况\n",
    "    \"\"\"\n",
    "    left = bin(i)[2:]    # 使用内置函数获取二进制数字符串\n",
    "    if len(left) < 8: \n",
    "        left = '{zeros}{left}'.format(zeros='0'*(8-len(left)), left=left)    # 如果不够8位补零\n",
    "    right = left[::-1]    # 翻转获得对称字符串\n",
    "    return left,right \n",
    "\n",
    "not_repeat_groups = {}    # 记录对称字符串转换为十进制没有数字重复的组合\n",
    "\n",
    "\n",
    "# 找出对称字符串转换为十进制后没有数字重复的组合\n",
    "for i in range(pow(2,8)): \n",
    "    left,right = change_10_to_2(i) \n",
    "    number10 = '{}{}'.format(int(left,2),int(right,2))\n",
    "    numberset = set(number10)    # set是集合，无序的不重复元素序列\n",
    "    if len(number10) == len(numberset):\n",
    "        not_repeat_groups[i] = numberset\n",
    "\n",
    "has_0_9_groups = set()    # 记录二进制字符串组合包含０-9数字且只出现一次的组合\n",
    "\n",
    "# 二进制字符串组合包含０-9数字且只出现一次的组合\n",
    "keys = list(not_repeat_groups.keys())\n",
    "values = list(not_repeat_groups.values())\n",
    "for i in range(len(values)): \n",
    "    for j in range(i, len(values)): \n",
    "        if len(values[i].union(values[j])) == 10:\n",
    "            has_0_9_groups.add((keys[i],keys[j]))\n",
    "\n",
    "\n",
    "result = set()  # 记录最终结果\n",
    "string_format = '{}.{}.{}.{}' \n",
    "for i in has_0_9_groups:\n",
    "    # 通过key,找到对应的二进制字符串\n",
    "    left1,left2 = i \n",
    "    right1 = int(change_10_to_2(left1)[1],2)\n",
    "    right2 = int(change_10_to_2(left2)[1],2) \n",
    "    # 排列位置不同，组合得到所有结果\n",
    "    result.add(string_format.format(left1,left2,right2,right1)) \n",
    "    result.add(string_format.format(left2,left1,right1,right2)) \n",
    "    result.add(string_format.format(right2,right1,left1,left2)) \n",
    "    result.add(string_format.format(right1,right2,left2,left1))\n",
    "\n",
    "# 打印结果\n",
    "print(result) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 数学运算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 求绝对值\n",
    "abs(-10)        # 10   \n",
    "# 用于创建一个值为 real + imag * j 的复数或者转化一个字符串或数为复数\n",
    "complex(1,2)    # (1+2j)\n",
    "complex('1+2j') # (1+2j)\n",
    "# 注意！这个地方在\"+\"号两边不能有空格，也就是不能写成\"1 + 2j\"，应该是\"1+2j\"，否则会报错"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 把除数和余数运算结果结合起来，返回一个包含商和余数的元组\n",
    "divmod(7,2)    # (3, 1)\n",
    "# 将整数和字符串转换成浮点数\n",
    "float('123')   # 123.0\n",
    "# 返回浮点数x的四舍五入值\n",
    "round(70.2322) # 70\n",
    "# 对系列进行求和计算\n",
    "sum([1,2,3])   # 6\n",
    "max([1,2,3])   # 3 获取最大值\n",
    "min([1,2,3])   # 1 获取最小值　"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all([1, 23, 4, 'a'])    #True 列表list，元素都不为空或0\n",
    "all(['a', 'b', '', 'd'])   #False 列表list，存在一个为空的元素\n",
    "all([0, 1, 2, 3])    #False 列表list，存在一个为0的元素\n",
    "all([None, 'a', 'c'])  #False　列表list，存在一个None元素\n",
    "all([])    # 空元组、空列表如：all([])返回值为True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "any(['a', '1', '', 'd'])   #True 列表list，存在一个为空的元素\n",
    "any([0, '', False])        #False 列表list,元素全为0,'',false\n",
    "any([])    #False 空列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 两个重要的常数\n",
    "print(math.pi)    # 圆周率\n",
    "print(math.e)    # 自然对数\n",
    "# 阶乘\n",
    "print(math.factorial(5))    #  5!=120 \n",
    "# 获取整数\n",
    "n = 100.7\n",
    "print(math.floor(n))  # 向下取整\n",
    "print(math.ceil(n))   # 向上取整\n",
    "print(math.trunc(n))  # 折断取整 \n",
    "# 求和\n",
    "values = [0.9999999, 1, 2, 3]\n",
    "print(sum(values))  # 6.999999900000001\n",
    "print(math.fsum(values))   # 6.9999999"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义矩阵变量并输出变量的一些属性\n",
    "# 用np.array()生成矩阵\n",
    "arr=np.array([[1,2,3],[4,5,6]])\n",
    "print(arr)\n",
    "print('维度: ',arr.ndim)\n",
    "print('形状: ',arr.shape)\n",
    "print('大小: ', arr.size)\n",
    "b = arr.reshape(3,2)\n",
    "print('修改后的数组：'  )\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：小花童的困惑"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "# 方法1：穷举所有可能，找最大公约数\n",
    "def gcd_1(m,n):\n",
    "    # 记录运算时间\n",
    "    start = time.clock()\n",
    "    # 找出较小的数\n",
    "    if m > n:\n",
    "        max_num = n\n",
    "    else:\n",
    "        max_num = m\n",
    "    # 记录结果，如果有比结果大的数就替换\n",
    "    gcd = 1\n",
    "    for i in range(2, max_num+1):\n",
    "        if m % i == 0 and n % i == 0:\n",
    "            gcd = i\n",
    "    \n",
    "    print(\"方法1运算时间：\", (time.clock() - start))\n",
    "    return gcd\n",
    "\n",
    "# 方法2：辗转相除法，又名欧几里德算法\n",
    "def gcd_2(m, n):\n",
    "    # 记录运算时间\n",
    "    start = time.clock()\n",
    "    if m < n:    # 我们希望m>=n\n",
    "        return gcd_2(n, m)\n",
    "    while n != 0:\n",
    "        print('{0} = {1} * {2} + {3}'.format(m, math.floor(m/n), n, m % n))\n",
    "        (m, n) = (n, m % n)\n",
    "    print('最大公约数: {}'.format(m)) \n",
    "    # 记录运算时间\n",
    "    print(\"方法2运算时间：\", (time.clock() - start))\n",
    "    return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(gcd_1(563060,32160))\n",
    "print(gcd_2(563060,32160))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(gcd_1(56,32))\n",
    "print(gcd_2(56,32))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：顽皮的图书管理员"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_pages(sum_page):\n",
    "    \"\"\"\n",
    "    sum_page表示输入的缺页书本页码数值总和\n",
    "    \"\"\"\n",
    "    page = 1    # 开始页码\n",
    "    total = 0   # 页码总和\n",
    "    while total < sum_page:\n",
    "        total += page\n",
    "        page += 1\n",
    "    print(\"这本书页码最大值:{}, 页码数值总和:{}\".format(page-1, total))\n",
    "    miss_page1 = 1    # 缺页页码数值\n",
    "    miss_page2 = 2    # 缺页页码数值\n",
    "    miss_page_sum = total - sum_page   # 缺页页码数值和\n",
    "    if miss_page_sum == 0:\n",
    "        print('没有缺页')   # 没有缺页就结束程序\n",
    "        return\n",
    "    has_find_page = False\n",
    "    while miss_page1 + miss_page2 <= miss_page_sum:\n",
    "        if miss_page1 + miss_page2 == miss_page_sum:\n",
    "            has_find_page = True\n",
    "            print(\"缺页页码为{}和{}\".format(miss_page1, miss_page2))\n",
    "            return\n",
    "        # 如果不符合条件，数值加1继续尝试\n",
    "        miss_page1 += 1\n",
    "        miss_page2 += 1\n",
    "    if not has_find_page:       \n",
    "        print(\"没有找到缺页\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "find_pages(858456584000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 特别的数字\n",
    "### 质数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prime_check_1(number):\n",
    "    \"\"\"\n",
    "    检查number是否为质数,如果是返回True, 否则返回False\n",
    "    \"\"\"\n",
    "    # 根据定义排除特殊例子\n",
    "    # 一个大于1的自然数，所以负数，0，1都不是质数\n",
    "    if number < 2:\n",
    "        return False\n",
    "    for i in range(2, number-1):\n",
    "        if number % i == 0:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prime_check_2(number):\n",
    "    if number < 2:\n",
    "        return False\n",
    "    # 2和3是比较特殊，2是唯一的偶数质数，3开方就是1，不符合判断公式\n",
    "    if number < 4:\n",
    "        return True\n",
    "    # 大于2的偶数当然不是质数，就不需要去穷举证明\n",
    "    if number % 2 == 0:\n",
    "        return False\n",
    "    \n",
    "    # 减少遍历的次数\n",
    "    odd_numbers = range(3, int(math.sqrt(number)) + 1, 2)\n",
    "    for i in odd_numbers:\n",
    "        if number % i == 0:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(prime_check_2(-1))\n",
    "print(prime_check_2(1))\n",
    "print(prime_check_2(2))\n",
    "print(prime_check_2(8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 水仙花数 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def narcissistic_3():\n",
    "    \"\"\"\n",
    "    水仙花数是指一个 3 位数，它的每个位上的数字的 3次幂之和等于它本身\n",
    "    \"\"\"\n",
    "    for number in range(100,1000):\n",
    "        a = int(number / 100)\n",
    "        b = int(number % 100 / 10)\n",
    "        c = int(number % 10)\n",
    "        \n",
    "        if pow(a,3)+pow(b,3)+pow(c,3) == number:\n",
    "            print(\"{}^3 + {}^3 + {}^3 = {}\".format(a,b,c,number))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def narcissistic_number(number): \n",
    "    \"\"\"\n",
    "    N位自幂数是指一个N位数，它的每个位上的数字的N次幂之和等于它本身\n",
    "    \"\"\"\n",
    "    print(type(number))\n",
    "    string_number = str(number)    \n",
    "    length = len(string_number)    \n",
    "    # 求出每一位的N次幂之和\n",
    "    sum_number = 0\n",
    "    for num in string_number: \n",
    "        sum_number += pow(int(num), length)\n",
    "    # 是否等于它本身   \n",
    "    if sum_number == number:           \n",
    "        print(\"%d是%d位自幂数\" % (number, length))\n",
    "    else:            \n",
    "        print(\"%d不是位自幂数\" % number)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "narcissistic_3()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPerfectNumber(number):\n",
    "    \"\"\"\n",
    "    输入一个大于1的整数\n",
    "    如果是完成数就返回True,如果不是则返回False\n",
    "    \"\"\"\n",
    "    if type(number) != int or number < 1:\n",
    "        print('n是非法输入，n必须是不少于1的整数')\n",
    "        return False\n",
    "    # 找出所有因子\n",
    "    divisors = []\n",
    "    for divisor in range(1,number):\n",
    "        if number % divisor == 0:\n",
    "            divisors.append(divisor)\n",
    "    print(divisors)\n",
    "    # sum求和整个队列，与原来的数比较大小\n",
    "    return sum(divisors) == number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "isPerfectNumber('sdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.11挑战：奇妙的数字"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_luck_number():\n",
    "    \"\"\"\n",
    "    寻找一个数字n, n^2和n^3把0~9的10个数字每个刚好只用了一次\n",
    "    \"\"\"\n",
    "    number = 1\n",
    "    number_string = \"\"\n",
    "    while len(number_string) < 11:\n",
    "        # 程序勇往直前，直到找到目标才退出\n",
    "        number_string = str(pow(number, 2)) + str(pow(number, 3))\n",
    "        if set(number_string) == set('0123456789'):\n",
    "            print(\"幸运号码:{}, 平方数:{}, 立方数:{}\".format(number, number**2, number**3))\n",
    "        number += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "find_luck_number()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数列\n",
    "\n",
    "### 等差数列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def arithmetic_sequence(n, a1, d):\n",
    "    \"\"\"等差数列\n",
    "    :n: 项数\n",
    "    :a1 首项\n",
    "    :d: 公差\"\"\"\n",
    "    if \"\" in (n,a1,d): # 简单的输入判断，避免程序因输入错误意外退出\n",
    "        return \"存在空白输入\"\n",
    "    series = []\n",
    "    for _ in range(int(n)):\n",
    "        # 计算数列项\n",
    "        if series == []:\n",
    "            series.append(a1)\n",
    "        else:\n",
    "            series.append(str(float(series[-1])+float(d))) \n",
    "    return series\n",
    "if __name__ == \"__main__\":\n",
    "    n = input(\"数列项数\") # 用交互方式获取参数，输入参数都是字符串类型\n",
    "    a1 = input(\"数列首项\")\n",
    "    d = input(\"数列公差\")\n",
    "    print(arithmetic_sequence(n, a1, d))\n",
    "    if "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(arithmetic_sequence(\"4\",\"2\",\"1\"))\n",
    "print(arithmetic_sequence(\"5\",\"2.1\",\"1.1\"))\n",
    "print(arithmetic_sequence(\"-1\",\"0\",\"2\"))\n",
    "print(arithmetic_sequence(\"0\",\"0\",\"0\"))\n",
    "print(arithmetic_sequence(\"1\",\"1\",\"\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 等比数列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def geometric_series(n, a1, q):\n",
    "    \"\"\"等差数列\n",
    "    :n: 项数\n",
    "    :a1 首项\n",
    "    :q: 公比\"\"\"\n",
    "    series = []\n",
    "    power = 1\n",
    "    multiple = q\n",
    "    for _ in range(n):\n",
    "        if series == []:\n",
    "            series.append(a1) # 首项\n",
    "        else:\n",
    "            power += 1\n",
    "            series.append(a1 * multiple)\n",
    "            multiple = pow(q, power)\n",
    "    return series # 返回数列所有项"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "series = geometric_series(64,1,2)\n",
    "total = sum(series) # 求数列的和\n",
    "print(\"一共是%d麦粒\" % total)\n",
    "total = total*0.03/1000/1000/10000\n",
    "print(\"也就是%.4f万吨\" % total)\n",
    "total / 13433.39"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 调和数列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import fsum # 使用fsum精确计算浮点数累加\n",
    "def harmonic_series(n):\n",
    "    \"\"\"调和数列，n为项数\"\"\"\n",
    "    series = []\n",
    "    for temp in range(int(n)):\n",
    "        # 1+1/2+1/3+1/4……+1/n+…… 第一个是1，其他1/(n+1)\n",
    "        series.append(1/(temp + 1) if series else 1)\n",
    "    return series\n",
    "\n",
    "def find_n(m):\n",
    "    \"\"\"找数列项数最小值n,使得调和级数大于ｍ\"\"\"\n",
    "    n = 1\n",
    "    total = 1\n",
    "    while total < m:\n",
    "        n += 1  # 项数\n",
    "        total = fsum(harmonic_series(n))\n",
    "    return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, 11):\n",
    "    print(\"S>{}, n={}\".format(i, find_n(i)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    \"\"\"递归求解斐波那契数列\"\"\"\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fibonacci(n - 1) + fibonacci(n - 2)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    max_n = int(input(\"项数\"))\n",
    "    if max_n > 0:\n",
    "        print([fibonacci(n) for n in range(max_n)])\n",
    "    else:\n",
    "        print(\"请输入大于0的正整数\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  杨辉三角"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pascal(depth):\n",
    "    \"\"\"杨辉三角\"\"\"\n",
    "    res = [[1]] # 第一层\n",
    "    for i in range(0, depth):\n",
    "        layer = [1] # 特性3:每一层都是１开始\n",
    "        for j in range(0, len(res[i]) - 1):\n",
    "            # 特性1:每个数等于它上方两数之和\n",
    "            layer.append(res[i][j] + res[i][j + 1]) \n",
    "        layer.append(1) # 特性3:每一层都是1结尾\n",
    "        res.append(layer) # 把每一层的数列加到结果中\n",
    "    return res\n",
    "\n",
    "def print_pascal(data):\n",
    "    \"\"\"输出杨辉三角\"\"\"\n",
    "    for squence in data:\n",
    "        total = 0 #一层数值求和结果\n",
    "        for i in squence:\n",
    "            total += i\n",
    "            print(i, end=' ')\n",
    "        print(\"=%d\" % total, end=' ') # end表示输出结尾\n",
    "        print()# 默认的输出结尾是\\n,回车另起一行。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(pascal(9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_pascal(pascal(9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pascal_to_fibonacci(data):\n",
    "    result = []\n",
    "    for n in range(len(data)):\n",
    "        fib = [] # 初始化每一层的数列，为空\n",
    "        m = 0\n",
    "        while n - m >= m:\n",
    "            # 根据定义，杨辉三角和斐波拉契数列的转化下标关系\n",
    "            # F(0) = C(0,0)\n",
    "            # F(1) = C(1,0)\n",
    "            # F(2) = C(2,0) + C(1,1)\n",
    "            fib.append(data[n-m][m])\n",
    "            m += 1\n",
    "        result.append(fib)\n",
    "    print_pascal(result) # 输出每一层的和        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pascal_to_fibonacci(pascal(6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 冰雹猜想"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def collatz_sequence(n):\n",
    "    \"\"\"冰雹猜想：记录数值变化的过程\"\"\"\n",
    "    sequence = [n]\n",
    "    while n != 1:# 猜想结果是，所有正整数都会回到1\n",
    "        if n % 2 == 0:  # 如果是偶数 N/2\n",
    "            n //= 2\n",
    "        else: # 如果是奇数 3N+1\n",
    "            n = 3 * n + 1 \n",
    "        sequence.append(n)\n",
    "    return sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "for _ in range(5): # 测试5个数值\n",
    "    print(collatz_sequence(randint(1,100))) # 随机挑选一个正整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 卡特兰数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def combination(n, m):\n",
    "    \"\"\"组合数公式：C(n,m) = n!/m!(n-m)!\"\"\"\n",
    "    result = 1  # 保存结果\n",
    "    # 组合数公式性质 C(n, m) = C(n, n-m)\n",
    "    if m > (n - m):\n",
    "        m = n - m\n",
    "    # 计算C(n,k)\n",
    "    for i in range(m):\n",
    "        result *= n - i\n",
    "        result //= i + 1\n",
    "    return result\n",
    "\n",
    "\n",
    "def catalan_number(n):\n",
    "    \"\"\"通过计算组合数推导出卡特兰数第n项的值，an=C(2n,n)/(n+1)\"\"\"\n",
    "    return combination(2 * n, n) // (n + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    print(catalan_number(i), end=',')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：百变二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    \"\"\"求解n的阶乘\"\"\"\n",
    "    result = 1\n",
    "    for i in range(1, n):\n",
    "        result = result * (i + 1)\n",
    "    return result\n",
    "    \n",
    "def variety_tree(n):\n",
    "    \"\"\"求解n个元素的二叉树变化数量\"\"\"\n",
    "    if n < 0:\n",
    "        print(\"n必须大于0\")\n",
    "        return\n",
    "    if n == 0: # 若为0，则输出0\n",
    "        return 0\n",
    "    return catalan_number(n) * factorial(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(-1, 10):\n",
    "    print(variety_tree(i), end=',')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
